# 1005.K次取反后最大化的数组和
# 给你一个整数数组nums和一个整数k ，按以下方法修改该数组：
# 选择某个下标i并将nums[i]替换为 - nums[i] 。重复这个过程恰好k次。可以多次选择同一个下标i 。以这种方式修改数组后，返回数组可能的最大和 。
#
# 示例1：
# 输入：nums = [4, 2, 3], k = 1
# 输出：5
# 解释：选择下标1 ，nums变为[4, -2, 3] 。
#
# 示例2：
# 输入：nums = [3, -1, 0, 2], k = 3
# 输出：6
# 解释：选择下标(1, 2, 2) ，nums变为[3, 1, 0, 2] 。
#
# 示例3：
# 输入：nums = [2, -3, -1, 5, -4], k = 2
# 输出：13
# 解释：选择下标(1, 4) ，nums变为[2, 3, -1, 5, 4] 。


class Solution:
    def largestSumAfterKNegations(self, nums:[int], k: int) -> int:
        # 确实不难, 我自己琢磨出来了,但是这个是贪心嘛
        nums.sort()
        su = 0
        size = len(nums)
        for i in range(size):
            if nums[i] < 0 and k > 0:
                nums[i] = -nums[i]
                k -= 1
            su += nums[i]
        odd = 1 if k % 2== 1 else 0
        if odd:
            mi = min(nums)
            su -= 2 * mi
        return su


    def largestSumAfterKNegations2(self, A: [int], K: int) -> int:
        # 卡哥题解里py的解法,思路和我有点不一样,但殊途同归
        A = sorted(A, key=abs, reverse=True) # 将A按绝对值从大到小排列
        for i in range(len(A)):
            if K > 0 and A[i] < 0:
                A[i] *= -1
                K -= 1
        if K > 0:
            A[-1] *= (-1)**K #取A最后一个数只需要写-1
        return sum(A)


if __name__ == '__main__':
    nums = [4,2,3]
    nums = [2,-3,-1,5,-4]
    k = 1
    tmp = Solution()
    res = tmp.largestSumAfterKNegations(nums,k)
    print(res)